Machine Learning and Knowledge Discovery in Databases
Knowledge discovery in databases is not only the nontrivial extraction of implicit, previously unknown and potentially useful information from databases. We argue that in contrast to machine learning, knowledge discovery in databases should be applied to real world databases. Since real world databases are known to be very large, they raise problems of the access. Therefore, real world databases only can be accessed by database management systems and the number of accesses has to be reduced to a minimum. Considering this property, we are forced to use, for example, standard set oriented interfaces of relational database management systems in order to apply methods of knowledge discovery in databases. We present a system for discovering data dependencies, which is build upon a set oriented interface. The point of main effort has been put on the discovery of value restrictions, unary inclusion- and functional dependencies in relational databases. The system also embodies an inference rel...
Machine Learning and Knowledge Discovery in Databases
Knowledge discovery in databases is not only the nontrivial extraction of implicit, previously unknown and potentially useful information from databases. We argue that in contrast to machine learning, knowledge discovery in databases should be applied to real world databases. Since real world databases are known to be very large, they raise problems of the access. Therefore, real world databases only can be accessed by database management systems and the number of accesses has to be reduced to a minimum. Considering this property, we are forced to use, for example, standard set oriented interfaces of relational database management systems in order to apply methods of knowledge discovery in databases. We present a system for discovering data dependencies, which is build upon a set oriented interface. The point of main effort has been put on the discovery of value restrictions, unary inclusion- and functional dependencies in relational databases. The system also embodies an inference rel...
Machine Learning and Knowledge Discovery in Databases
Knowledge discovery in databases is not only the nontrivial extraction of implicit, previously unknown and potentially useful information from databases. We argue that in contrast to machine learning, knowledge discovery in databases should be applied to real world databases. Since real world databases are known to be very large, they raise problems of the access. Therefore, real world databases only can be accessed by database management systems and the number of accesses has to be reduced to a minimum. Considering this property, we are forced to use, for example, standard set oriented interfaces of relational database management systems in order to apply methods of knowledge discovery in databases. We present a system for discovering data dependencies, which is build upon a set oriented interface. The point of main effort has been put on the discovery of value restrictions, unary inclusion- and functional dependencies in relational databases. The system also embodies an inference rel...
Machine Learning and Knowledge Discovery in Databases
Knowledge discovery in databases is not only the nontrivial extraction of implicit, previously unknown and potentially useful information from databases. We argue that in contrast to machine learning, knowledge discovery in databases should be applied to real world databases. Since real world databases are known to be very large, they raise problems of the access. Therefore, real world databases only can be accessed by database management systems and the number of accesses has to be reduced to a minimum. Considering this property, we are forced to use, for example, standard set oriented interfaces of relational database management systems in order to apply methods of knowledge discovery in databases. We present a system for discovering data dependencies, which is build upon a set oriented interface. The point of main effort has been put on the discovery of value restrictions, unary inclusion- and functional dependencies in relational databases. The system also embodies an inference rel...
Cold start link prediction.
Inthetraditionallinkpredictionproblem, asnapshotofasocial network is used as a starting point to predict, by means of graph-theoretic measures, the links that are likely to appear in the future. In this paper, we introduce cold start link prediction as the problem of predicting the structure of a social network when the network itself is totally missing while some other information regarding the nodes is available. Weproposeatwo-phasemethodbasedonthebootstrap probabilistic graph. The first phase generates an implicit social network under the form of a probabilistic graph. The second phase applies probabilistic graph-based measures to produce the final prediction. We assess our method empirically over a large data collection obtained from Flickr, using interest groups as the initial information. The experiments confirm the effectiveness of our approach.
Fast Katz and Commuters Efficient Estimation of Social Relatedness in Large Networks.
Abstract. Motivated by social network data mining problems such as link prediction and collaborative filtering, significant research effort has been devoted to computing topological measures including the Katz score and the commute time. Existing approaches typically approximate all pairwise relationships simultaneously. In this paper, we are interested in computing: the score for a single pair of nodes, and the top-k nodes with the best scores from a given source node. For the pairwise problem, we apply an iterative algorithm that computes upper and lower bounds for the measures we seek. This algorithm exploits a relationship between the Lanczos process and a quadrature rule. For the top-k problem, we propose an algorithm that only accesses a small portion of the graph and is related to techniques used in personalized PageRank computing. To test the scalability and accuracy of our algorithms we experiment with three real-world networks and find that these algorithms run in milliseconds to seconds without any preprocessing. 1
Learning influence probabilities in social networks.
Recently, there has been tremendous interest in the phenomenon of influence propagation in social networks. The studies in this area assume they have as input to their problems a social graph with edges labeled with probabilities of influence between users. However, the question of where these probabilities come from or how they can be computed from real social network data has been largely ignored until now. Thus it is interesting to ask whether from a social graph and a log of actions by its users, one can build models of influence. This is the main problem attacked in this paper. In addition to proposing models and algorithms for learning the model parameters and for testing the learned models to make predictions, we also develop techniques for predicting the time by which a user may be expected to perform an action. We validate our ideas and techniques using the Flickr data set consisting of a social graph with 1.3M nodes, 40M edges, and an action log consisting of 35M tuples referring to 300K distinct actions. Beyond showing that there is genuine influence happening in a real social network, we show that our techniques have excellent prediction performance.
Do you want to take notes%3F identifying research missions in Yahoo%21 search pad.

On the high density of leadership nuclei in endorsement social networks.

Do you want to take notes%3F identifying research missions in Yahoo%21 search pad.

Approximation Analysis of Influence Spread in Social Networks

Guest editors%27 introduction special issue of selected papers from ECML PKDD 2010.

Learning and Predicting the Evolution of Social Networks.

Hiding Sequential and Spatiotemporal Patterns.

Hiding Sequential and Spatiotemporal Patterns.



Special issue for ECML PKDD 2010 Guest editors%27 introduction.

k%2DNearest Neighbors in Uncertain Graphs.
Complex networks, such as biological, social, and communication networks, often entail uncertainty, and thus, can be modeled as probabilistic graphs. Similar to the problem of similarity search in standard graphs, a fundamental problem for probabilistic graphs is to efficiently answer k-nearest neighbor queries (k-NN), which is the problem of computing the k closest nodes to some specific node. In this paper we introduce a framework for processing k-NN queries in probabilistic graphs. We propose novel distance functions that extend well-known graph concepts, such as shortest paths. In order to compute them in probabilistic graphs, we design algorithms based on sampling. During k-NN query processing we efficiently prune the search space using novel techniques. Our experiments indicate that our distance functions outperform previously used alternatives in identifying true neighbors in real-world biological data. We also demonstrate that our algorithms scale for graphs with tens of millions of edges. 1.
Privacy
Each of two parties PX and P Y holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x; y). That is, PX should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value, f(x; y), and similarly, P Y should not learn any additional information about x.  In this paper we consider two basic questions in the theory of private computations: 1. Which functions can be privately computed ? 2. What is the communication complexity of protocols that privately compute a function  f (in the case that such protocols exist) ? A complete combinatorial characterization of privately computable functions is given. We use this characterization to derive tight bounds on the rounds complexity of any privately computable function, and to design optimal private protocols that compute these functions. We show that for every 1  g(n)  2 \Delta 2  n  there are functions that can be privately...
Compressing tags to find interesting media groups.
On photo sharing websites like Flickr and Zooomr, users are offered the possibility to assign tags to their uploaded pictures. Using these tags to find interesting groups of semantically related pictures in the result set of a given query is a problem with obvious applications. We analyse this problem from a Minimum Description Length (MDL) perspective and develop an algorithm that finds the most interesting groups. The method is based on Krimp, which finds small sets of patterns that characterise the data using compression. These patterns are sets of tags, often assigned together to photos. The better a database compresses, the more structure it contains and thus the more homogeneous it is. Following this observation we devise a compression-based measure. Our experiments on Flickr data show that the most interesting and homogeneous groups are found. We show extensive examples and compare to clusterings on the Flickr website.
Voting in social networks.
A voting system is a set of rules that a community adopts to take collective decisions. In this paper we study voting systems for a particular kind of community: electronically mediated social networks. In particular, we focus on delegative democracy (a.k.a. proxy voting) that has recently received increased interest for its ability to combine the benefits of direct and representative systems, and that seems also perfectly suited for electronically mediated social networks. In such a context, we consider a voting system in which users can only express their preference for one among the people they are explicitly connected with, and this preference can be propagated transitively, using an attenuation factor. We present this system and we study its properties. We also take into consideration the problem of missing votes, which is particularly relevant in online networks, as some recent case shows. Our experiments on real-world networks provide interesting insight into the significance and stability of the results obtained with the suggested voting system.
Fast shortest path distance estimation in large networks.

Mining Graph Evolution Rules.

Taxonomy%2DDriven Lumping for Sequence Mining.
Abstract Given a taxonomy of events and a dataset of sequences of these events, we study the problem of finding efficient and effective ways to produce a compact representation of the sequences. We model sequences with Markov models whose states correspond to nodes in the provided taxonomy, and each state represents the events in the subtree under the corresponding node. By lumping observed events to states that correspond to internal nodes in the taxonomy, we allow more compact models that are easier to understand and visualize, at the expense of a decrease in the data likelihood. We formally define and characterize our problem, and we propose a scalable search method for finding a good trade-off between two conflicting goals: maximizing the data likelihood, and minimizing the model complexity. We implement these ideas in Taxomo, a taxonomy-driven modeler, which we apply in two different domains, query-log mining and mining of moving-object trajectories. The empirical evaluation confirms the feasibility and usefulness of our approach. Keywords Data mining · Sequence analysis · Markov models · Query-log analysis · Spatial-data analysis
Anonymizing moving objects how to hide a MOB in a crowd%3F
Moving object databases (MOD) have gained much interest in recent years due to the advances in mobile communications and positioning technologies. Study of MOD can reveal useful information (e.g., traffic patterns and congestion trends) that can be used in applications for the common benefit. In order to mine and/or analyze the data, MOD must be published, which can pose a threat to the location privacy of a user. Indeed, based on prior knowledge of a user’s location at several time points, an attacker can potentially associate that user to a specific moving object (MOB) in the published database and learn her position information at other time points. In this paper, we study the problem of privacy-preserving publishing of moving object database. Unlike in microdata, we argue that in MOD, there does not exist a fixed set of quasi-identifier (QID) attributes for all the MOBs. Consequently the anonymization groups of MOBs (i.e., the sets of other MOBs within which to hide) may not be disjoint. Thus, there may exist MOBs that can be identified explicitly by combining different anonymization groups. We illustrate the pitfalls of simple adaptations of classical k-anonymity and develop a notion which we prove is robust against privacy attacks. We propose two approaches, namely extremeunion and symmetric anonymization, to build anonymization groups that provably satisfy our proposed k-anonymity requirement, as well as yield low information loss. We ran an extensive set of experiments on large real-world and synthetic datasets of vehicular traffic. Our results demonstrate the effectiveness of our approach. 1.
GuruMine A Pattern Mining System for Discovering Leaders and Tribes.

Privacy Preserving Publication of Moving Object Data.

A new technique for sequential pattern mining under regular expressions.

From %22Dango%22 to %22Japanese Cakes%22 Query Reformulation Models and Patterns.
Abstract—Understanding query reformulation patterns is a key step towards next generation web search engines: it can help improving users ’ web-search experience by predicting their intent, and thus helping them to locate information more effectively. As a step in this direction, we build an accurate model for classifying user query reformulations into broad classes (generalization, specialization, error correction or parallel move), achieving 92 % accuracy. We apply the model to automatically label two large query logs, creating annotated queryflow graphs. We study the resulting reformulation patterns, finding results consistent with previous studies done on smaller manually annotated datasets, and discovering new interesting patterns, including connections between reformulation types and topical categories. Finally, applying our findings to a third query log that is publicly available for research purposes, we demonstrate that our reformulation classifier leads to improved recommendations in a query recommendation system. I.
Mining Clinical%2C Immunological%2C and Genetic Data of Solid Organ Transplantation.

Taxonomy%2Ddriven lumping for sequence mining.
Abstract Given a taxonomy of events and a dataset of sequences of these events, we study the problem of finding efficient and effective ways to produce a compact representation of the sequences. We model sequences with Markov models whose states correspond to nodes in the provided taxonomy, and each state represents the events in the subtree under the corresponding node. By lumping observed events to states that correspond to internal nodes in the taxonomy, we allow more compact models that are easier to understand and visualize, at the expense of a decrease in the data likelihood. We formally define and characterize our problem, and we propose a scalable search method for finding a good trade-off between two conflicting goals: maximizing the data likelihood, and minimizing the model complexity. We implement these ideas in Taxomo, a taxonomy-driven modeler, which we apply in two different domains, query-log mining and mining of moving-object trajectories. The empirical evaluation confirms the feasibility and usefulness of our approach. Keywords Data mining · Sequence analysis · Markov models · Query-log analysis · Spatial-data analysis
A constraint%2Dbased querying system for exploratory pattern discovery.

Privacy
Each of two parties PX and P Y holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x; y). That is, PX should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value, f(x; y), and similarly, P Y should not learn any additional information about x.  In this paper we consider two basic questions in the theory of private computations: 1. Which functions can be privately computed ? 2. What is the communication complexity of protocols that privately compute a function  f (in the case that such protocols exist) ? A complete combinatorial characterization of privately computable functions is given. We use this characterization to derive tight bounds on the rounds complexity of any privately computable function, and to design optimal private protocols that compute these functions. We show that for every 1  g(n)  2 \Delta 2  n  there are functions that can be privately...
Privacy
Each of two parties PX and P Y holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x; y). That is, PX should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value, f(x; y), and similarly, P Y should not learn any additional information about x.  In this paper we consider two basic questions in the theory of private computations: 1. Which functions can be privately computed ? 2. What is the communication complexity of protocols that privately compute a function  f (in the case that such protocols exist) ? A complete combinatorial characterization of privately computable functions is given. We use this characterization to derive tight bounds on the rounds complexity of any privately computable function, and to design optimal private protocols that compute these functions. We show that for every 1  g(n)  2 \Delta 2  n  there are functions that can be privately...
Discovering leaders from community actions.
We introduce a novel frequent pattern mining approach to discover leaders and tribes in social networks. In particular, we consider social networks where users perform actions. Actions may be as simple as tagging resources (urls) as in del.icio.us, rating songs as in Yahoo! Music, or movies as in Yahoo! Movies, or users buying gadgets such as cameras, handhelds, etc. and blogging a review on the gadgets. The assumption is that actions performed by a user can be seen by their network friends. Users seeing their friends ’ actions are sometimes tempted to perform those actions. We are interested in the problem of studying the propagation of such “influence”, and on this basis, identifying which users are leaders when it comes to setting the trend for performing various actions. We consider alternative definitions of leaders based on frequent patterns and develop algorithms for their efficient discovery. Our definitions are based on observing the way influence propagates in a time window, as the window is moved in time. Given a social graph and a table of user actions, our algorithms can discover leaders of various flavors by making one pass over the actions table. We run detailed experiments to evaluate the utility and scalability of our algorithms on real-life data. The results of our experiments confirm on the one hand, the efficiency of the proposed algorithm, and on the other hand, the effectiveness and relevance of the overall framework. To the best of our knowledge, this the first frequent pattern based approach to social network mining.
The query%2Dflow graph model and applications.
Query logs record the queries and the actions of the users of search engines, and as such they contain valuable information about the interests, the preferences, and the behavior of the users, as well as their implicit feedback to search-engine results. Mining the wealth of information available in the query logs has many important applications including querylog analysis, user profiling and personalization, advertising, query recommendation, and more. In this paper we introduce the query-flow graph, a graph representation of the interesting knowledge about latent querying behavior. Intuitively, in the query-flow graph a directed edge from query qi to query qj means that the two queries are likely to be part of the same “search mission”. Any path over the query-flow graph may be seen as a searching behavior, whose likelihood is given by the strength of the edges along the path. The query-flow graph is an outcome of query-log mining and, at the same time, a useful tool for it. We propose a methodology that builds such a graph by mining time and textual information as well as aggregating queries from different users. Using this approach we build a real-world queryflow graph from a large-scale query log and we demonstrate its utility in concrete applications, namely, finding logical sessions, and query recommendation. We believe, however, that the usefulness of the query-flow graph goes beyond these two applications.
Never Walk Alone Uncertainty for Anonymity in Moving Objects Databases.
Abstract — Preserving individual privacy when publishing data is a problem that is receiving increasing attention. According to the k-anonymity principle, each release of data must be such that each individual is indistinguishable from at least k −1 other individuals. In this paper we study the problem of anonymity preserving data publishing in moving objects databases. We propose a novel concept of k-anonymity based on co-localization that exploits the inherent uncertainty of the moving object’s whereabouts. Due to sampling and positioning systems (e.g., GPS) imprecision, the trajectory of a moving object is no longer a polyline in a three-dimensional space, instead it is a cylindrical volume, where its radius δ represents the possible location imprecision: we know that the trajectory of the moving object is within this cylinder, but we do not know exactly where. If another object moves within the same cylinder they are indistinguishable from each other. This leads to the definition of (k, δ)-anonymity for moving objects databases. We first characterize the (k, δ)-anonymity problem and discuss techniques to solve it. Then we focus on the most promising technique by the point of view of information preservation, namely space translation. We develop a suitable measure of the information distortion introduced by space translation, and we prove that the problem of achieving (k, δ)-anonymity by space translation with minimum distortion is NP-hard. Faced with the hardness of our problem we propose a greedy algorithm based on clustering and enhanced with ad hoc pre-processing and outlier removal techniques. The resulting method, named N WA (N ever Walk Alone), is empirically evaluated in terms of data quality and efficiency. Data quality is assessed both by means of objective measures of information distortion, and by comparing the results of the same spatio-temporal range queries executed on the original database and on the (k, δ)-anonymized one. Experimental results show that for a wide range of values of δ and k, the relative error introduced is kept low, confirming that N WA produces high quality (k, δ)-anonymized data.
Sequence Mining Automata A New Technique for Mining Frequent Sequences under Regular Expressions.
In this paper we study the problem of mining frequent sequences satisfying a given regular expression. Previous approaches to solve this problem were focusing on its search space, pushing (in some way) the given regular expression to prune unpromising candidate patterns. On the contrary, we focus completely on the given input data and regular expression. We introduce Sequence Mining Automata (SMA), a specialized kind of Petri Net that while reading input sequences, it produces for each sequence all and only the patterns contained in the sequence and that satisfy the given regular expression. Based on this automaton, we develop a family of algorithms. Our thorough experimentation on different datasets and application domains confirms that in many cases our methods outperform the current state of the art of frequent sequence mining algorithms using regular expressions (in some cases of orders of magnitude). 1.
Topical query decomposition.
We introduce the problem of query decomposition, where we are given a query and a document retrieval system, and we want to produce a small set of queries whose union of resulting documents corresponds approximately to that of the original query. Ideally, these queries should represent coherent, conceptually well-separated topics. We provide an abstract formulation of the query decomposition problem, and we tackle it from two different perspectives. We first show how the problem can be instantiated as a specific variant of a set cover problem, for which we provide an efficient greedy algorithm. Next, we show how the same problem can be seen as a constrained clustering problem, with a very particular kind of constraint, i.e., clustering with predefined clusters. We develop a two-phase algorithm based on hierarchical agglomerative clustering followed by dynamic programming. Our experiments, conducted on a set of actual queries in a Web scale search engine, confirm the effectiveness of the proposed solutions.
Privacy Protection Regulations and Technologies%2C Opportunities and Threats.

Privacy in Spatiotemporal Data Mining.

Recent advances in preserving privacy when mining data.

PinKDD%2708 privacy%2C security%2C and trust in KDD post workshop report.
This report summarizes the events of the 2 nd International
Anonymity preserving pattern discovery.

Mining Clinical Data with a Temporal Dimension A Case Study.

Hiding Sequences.
This paper reports on the development and formal certification (proof of semantic preservation) of a compiler from Cminor (a C-like imperative language) to PowerPC assembly code, using the Coq proof assistant both for programming the compiler and for proving its correctness. Such a certified compiler is useful in the context of formal methods applied to the certification of critical software: the certification of the compiler guarantees that the safety properties proved on the source code hold for the executable compiled code as well.  
Hiding Sequences.
This paper reports on the development and formal certification (proof of semantic preservation) of a compiler from Cminor (a C-like imperative language) to PowerPC assembly code, using the Coq proof assistant both for programming the compiler and for proving its correctness. Such a certified compiler is useful in the context of formal methods applied to the certification of critical software: the certification of the compiler guarantees that the safety properties proved on the source code hold for the executable compiled code as well.  
Time%2DAnnotated Sequences for Medical Data Mining.

Hiding Sensitive Trajectory Patterns.
Abstract. Sequential pattern mining is a major research field in knowledge discovery and data mining. Thanks to the increasing availability of transaction data, it is now possible to provide new and improved services based on users ’ and customers ’ behavior. However, this puts the citizen’s privacy at risk. Thus, it is important to develop new privacy-preserving data mining techniques that do not alter the analysis results significantly. In this paper we propose a new approach for anonymizing sequential data by hiding infrequent, and thus potentially sensible, subsequences. Our approach guarantees that the disclosed data are k-anonymous and preserve the quality of extracted patterns. An application to a real-world moving object database is presented, which shows the effectiveness of our approach also in complex contexts. 1
Privacy%2DAware Knowledge Discovery from Location Data.

Hiding Sequences.
This paper reports on the development and formal certification (proof of semantic preservation) of a compiler from Cminor (a C-like imperative language) to PowerPC assembly code, using the Coq proof assistant both for programming the compiler and for proving its correctness. Such a certified compiler is useful in the context of formal methods applied to the certification of critical software: the certification of the compiler guarantees that the safety properties proved on the source code hold for the executable compiled code as well.  
Towards Constraint%2DBased Subgraph Mining.

Extending the state%2Dof%2Dthe%2Dart of constraint%2Dbased pattern discovery.


Soft constraint based pattern mining.
Abstract. The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focussed on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. As a solution, in this paper we introduce the new paradigm of pattern discovery based on Soft Constraints. Albeit simple, the proposed paradigm overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery. 1 Background and Motivations During the last decade a lot of researchers have focussed their (mainly algorithmic) investigations on the computational problem of Frequent Pattern Discovery, i.e. mining

Knowledge Discovery in Inductive Databases

Mining HLA Patterns Explaining Liver Diseases.

ConQueSt a Constraint%2Dbased Querying System for Exploratory Pattern Discovery.

On Interactive Pattern Mining from Relational Databases.
Clustering is an important tool for data mining, since it can  identify major patterns or trends without any supervision (labeled data).
Towards low%2Dperturbation anonymity preserving pattern discovery.

On Interactive Pattern Mining from Relational Databases.
Clustering is an important tool for data mining, since it can  identify major patterns or trends without any supervision (labeled data).
On condensed representations of constrained frequent patterns.

Pushing Tougher Constraints in Frequent Pattern Mining.
In this paper we extend the state-of-art of the constraints that can be pushed in a frequent pattern computation. We introduce a new class of tough constraints, namely Loose Anti-monotone constraints, and we deeply characterize them by showing that they are a superclass of convertible anti-monotone constraints (e.g. constraints on average or median) and that they model tougher constraints (e.g. variance or standard deviation) which have never been studied before. Then we show how these constraints can be exploited in a levelwise Apriori-like computation by means of new datareduction strategies, outperforming previous algorithms for tough constraints, and exploiting much tougher ones with the same effectiveness.
k%2DAnonymous Patterns.
Abstract. It is generally believed that data mining results do not violate the anonymity of the individuals recorded in the source database. In fact, data mining models and patterns, in order to ensure a required statistical significance, represent a large number of individuals and thus conceal individual identities: this is the case of the minimum support threshold in association rule mining. In this paper we show that this belief is ill-founded. By shifting the concept of k-anonymity from data to patterns, we formally characterize the notion of a threat to anonymity in the context of pattern discovery, and provide a methodology to efficiently and effectively identify all possible such threats that might arise from the disclosure of a set of extracted patterns. 1
Interestingness is Not a Dichotomy Introducing Softness in Constrained Pattern Mining.
Abstract. The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focussed on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. As a solution, in this paper we introduce the new paradigm of pattern discovery based on Soft Constraints. Albeit simple, the proposed paradigm overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery. 1 Background and Motivations During the last decade a lot of researchers have focussed their (mainly algorithmic) investigations on the computational problem of Frequent Pattern Discovery, i.e. mining
Anonymity and data mining.
“Although nature commences with reason and ends with experience it is necessary for us to do the opposite, that is to commence with experience and from this to proceed to investigate the reason.” This thesis investigates two new research problems that arise in modern data mining: reasoning on data mining results, and privacy implication of data mining results. Most of the data mining algorithms rely on inductive techniques, trying to infer information that is generalized from the input data. But very often this inductive step on raw data is not enough to answer the user questions, and there is the need to process data again using other inference methods. In order to answer high level user needs such as explanation of results, we describe an environment able to perform abductive (hypothetical) reasoning, since often the solutions of such queries can be seen as the set of hypothesis that satisfy some requirements. By using cost-based abduction, we show how classification algorithms can be boosted by performing abductive reasoning over the data mining results, improving the quality
Exante A Preprocessing Method for Frequent%2DPattern Mining.

Efficient breadth%2Dfirst mining of frequent pattern with monotone constraints.

A Relational Query Primitive for Constraint%2DBased Pattern Mining.

On Closed Constrained Frequent Pattern Mining.
Constrained frequent patterns and closed frequent patterns are two paradigms aimed at reducing the set of extracted patterns to a smaller, more interesting, subset. Although a lot of work has been done with both these paradigms, there is still confusion around the mining problem obtained by joining closed and constrained frequent patterns in a unique framework. In this paper we shed light on this problem by providing a formal definition and a thorough characterization. We also study computational issues and show how to combine the most recent results in both paradigms, providing a very efficient algorithm which exploits the two requirements (satisfying constraints and being closed) together at mining time in order to reduce the computation as much as possible. 1.
Pushing Constraints to Detect Local Patterns.

FP%2DBonsai The Art of Growing and Pruning Small FP%2DTrees.
In the context of mining frequent itemsets, numerous strategies  have been proposed to push several types of constraints within the  most well known algorithms. In this paper, we integrate the recently  proposed ExAnte data reduction technique within the FP-growth algorithm.
Frequent Pattern Queries for Flexible Knowledge Discovery.

ExAMiner Optimized Level%2Dwise Frequent Pattern Mining with Monotone Constraint.
The key point of this paper is that, in frequent pattern mining, the most appropriate way of exploiting monotone constraints in conjunction with frequency is to use them in order to reduce the problem input together with the search space. Following this intuition, we introduce ExAMiner, a level-wise algorithm which exploits the real synergy of antimonotone and monotone constraints: the total benefit is greater than the sum of the two individual benefits. ExAMiner generalizes the basic idea of the preprocessing algorithm ExAnte [4], embedding such ideas at all levels of an Apriori-like computation. The resulting algorithm is the generalization of the Apriori algorithm when a conjunction of monotone constraints is conjoined to the frequency antimonotone constraint. Experimental results confirm that this is, so far, the most efficient way of attacking the computational problem in analysis.
Adaptive Constraint Pushing in Frequent Pattern Mining.
Abstract. Pushing monotone constraints in frequent pattern mining can help pruning the search space, but at the same time it can also reduce the effectiveness of anti-monotone pruning. There is a clear tradeoff. Is it better to exploit more monotone pruning at the cost of less antimonotone pruning, or viceversa? The answer depends on characteristics of the dataset and the selectivity of constraints. In this paper, we deeply characterize this trade-off and its related computational problem. As a result of this characterization, we introduce an adaptive strategy, named ACP (Adaptive Constraint Pushing) which exploits any conjunction of monotone and anti-monotone constraints to prune the search space, and level by level adapts the pruning to the input dataset and constraints, in order to maximize efficiency. 1
ExAnte Anticipated Data Reduction in Constrained Pattern Mining.
Constraint pushing techniques have been proven to be e#ective  in reducing the search space in the frequent pattern mining task,  and thus in improving e#ciency. But while pushing anti-monotone constraints  in a level-wise computation of frequent itemsets has been recognized  to be always profitable, the case is di#erent for monotone constraints.
Pre%2Dprocessing for Constrained Pattern Mining.

Data Mining for Intelligent Web Caching.
The paper presents a vertical application of data warehousing and data mining technology:  intelligent web caching. We introduce several ways to construct intelligent web  caching algorithms that employ predictive models of web requests; the general idea is to  extend the LRU policy of web and proxy servers by making it sensible to web access models  extracted from web log data using data mining techniques. Two approaches have been  studied in particular, one based on association rules and another based on decision trees.
Web log data warehousing and mining for intelligent web caching.
We introduce intelligent web caching algorithms that employ predictive models of web requests; the general idea is to extend the LRU policy of web and proxy servers by making it sensible to web access models extracted from web log data using data mining techniques. Two approaches have been studied in particular, frequent patterns and decision trees. The experimental results of the new algorithms show substantial improvement over existing LRU-based caching techniques, in terms of hit rate. We designed and developed a prototypical system, which supports data warehousing of web log data, extraction of data mining models and simulation of the web caching algorithms.
On Verification in Logic Database Languages.

Using Data Mining Techniques in Fiscal Fraud Detection.
. Planning adequate audit strategies is a key success factor in &#034;a  posteriori&#034; fraud detection, e.g., in the fiscal and insurance domains, where  audits are intended to detect tax evasion and fraudulent claims. A case study is  presented in this paper, which illustrates how techniques based on classification  can be used to support the task of planning audit strategies. The proposed  approach is sensible to some conflicting issues of audit planning, e.g., the tradeoff  between maximizing audit benefits vs. minimizing audit costs.  1 Introduction  Fraud detection is becoming a central application area for knowledge discovery in databases, as it poses challenging technical and methodological problems, many of which are still open [1, 2]. A major task in fraud detection is that of constructing models, or profiles, of fraudulent behavior, which may serve in decision support systems for:  . preventing frauds (a priori fraud detection), or  . planning audit strategies (a posteriori fraud de...
A Classification%2DBased Methodology for Planning Audit Strategies in Fraud Detection.
Planning adequate audit strategies is a key success factor in a posterion ’ fraud detection, e.g., in the fiscal and insurance domains, where audits are intended to detect tax evasion and fraudulent claims. A case study is presented in this paper, which illustrates how techniques based on classification can be used to support the task of planning audit strategies. The proposed approach is sensible to some conflicting issues of audit planning, e.g., the trade-off between maximizing audit benefits vs. minimizing audit costs. A methodological scenario, common to a whole class of similar applications, is then abstracted away from the case study. The limitations of available systems to support the identified overall KDD process, bring us to point out the key aspects of a logic-based database language, integrated with mining mechanisms, which is used to provide a uniform, highly expressive environment for the various steps in the construction of the considered case-study. Keywords Knowledge discovery in databases, data mining, classification, decision trees, fraud detection, logic-based database languages, integration of querying and mining. 1.
Una Metodologia Basata sulla Classificazione per la Pianificazione degli Accertamenti nel Rilevamento di Frodi.

